package 滑动窗口And双指针.双指针.快慢指针;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/3 13:28
 */
public class leetcode645错误的集合 {
    /*
     简单version
     进阶Version
     */

    /*
     简单 版本
     这里使用 stream 有点不太 合适!
     */
    public int simpleVersion(int nums[]){
        return Math.abs(Arrays.stream(nums).distinct().sum() - (1 + nums.length));
    }



        /*
     时间复杂度 O(N)
     空间复杂度 O(N)
     思路 也非常的 巧妙的
     */
        public int[] solution(int nums[]){
            int len = nums.length,lost = -1,repeat = 0,sum = 0,map[] = new int[len + 1];
            for(int num : nums){
                if(map[num] != 0){
                    repeat  = num;
                }
                sum += num;
                map[num]++;
            }
            int shouldSum = (1 + len) * len >> 1;
            return new int[] {lost = shouldSum + repeat - sum,repeat};
        }







        /*
          思想 错了,  这个 题 发现 根本  就无法使用 ** 快慢指针 ** 来解决 环形 链表的 思想 **  来解决 ,有问题!
          看着 好像 可以 用 ** 数 组 映射链表的 方式解决 但是,根本就 实现不了 **

          ==

          原地 哈希: 来实现 时间复杂度 O(N) , 空间复杂度 O(1)
          附属 一个 大神的 链接:
          https://leetcode.cn/problems/set-mismatch/solutions/1509967/645-cuo-wu-de-ji-he-by-stormsunshine-z2gh/?orderBy=newest_to_oldest&topicTags=linked-list%2Chash-table
          */











    // 该题 使用下面的 思想 根本解决不了!
    /*
     快慢指针, 先找出 , 这个 重复的 元素, 也就是 环的 入口地址, ( 注意  链表中的 指针 , 对应 着 数组的 下标 (相当于 把 数组下标 看成 指针))
     为什么 该 数组 arr 能够映射成 链表,  数组 长度  n , arr[i] 的范围 是 1 ~ n, 正因为 这种特殊性
     */

    /*
    时间 复杂度 O(N)
    空间复杂度 O(1)
    主要是  实现 上面 这 中 复杂度的要求:
    ==
     这个 题 和 lc 287 寻找 重复的数字 还有些 , 不一样,
     这个 代码  coding 要 复杂的 多
     */
    public int [] solutionNew(int nums[]){
        int slow = nums[0],fast = nums[0];
        while(true){
            slow = nums[slow] - 1;
            fast = nums[nums[fast] - 1] - 1;
            if(slow == fast){
                slow = nums[0];
                while(slow != fast){
                    slow = nums[slow] - 1;
                    fast = nums[fast] - 1;
                }
                break; // at the moment , slow is repeatValue
            }
        }
        // 还需要 求和
        int sum = Arrays.stream(nums).sum();
        int shouldSum = (1 + nums.length) * nums.length >> 1;
        return new int[]{slow, shouldSum + slow - sum};
    }





}
